\documentclass[a4paper,10pt]{article}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage[latin1]{inputenc}
\usepackage[spanish]{babel}

\title{ \textbf{ 6620. Organizaci\'on de Computadoras\\
Trabajo Pr\'actico 1: \\Conjunto de instrucciones MIPS}}

\author{	Romeo, Mauro, \textit{Padr\'on Nro. 89.368} \\
            	\texttt{ mauropromeo@hotmail.com } \\[2.5ex]
            	Arg\"uello, Osiris, \textit{Padr\'on Nro. 83.062} \\
            	\texttt{ osirisarguello@gmail.com } \\[2.5ex]
		Constantino, Guillermo, \textit{Padr\'on Nro. 89.776} \\
		\texttt{ guilleconstantino@gmail.com } \\[2.5ex]
            	\normalsize{1er. Cuatrimestre de 2014} \\
            	\normalsize{66.20 Organizaci\'on de Computadoras  $-$ Pr\'atica Jueves} \\
            	\normalsize{Facultad de Ingenier\'ia, Universidad de Buenos Aires} \\
       }

\date{}

\begin{document}
\maketitle
\thispagestyle{empty}  % quita el nmero en la primer pagina


\begin{abstract}
El presente trabajo tiene como objetivo familiarizarse con la programaci\'on en assembly y el concepto de ABI, implementando una versi\'on simplificada de wc.

\end{abstract}
\pagebreak

\setcounter{page}{2}
\section{Introducci\'on}
El presente trabajo tiene como objetivo implementar una versi\'on simplificada del programa wc, utilizando un programa en lenguaje C que realiza llamadas a m\'etodos programados en assembly. Estos m\'etodos deber\'an cumplir con la ABI proporcionada por la catedra y nos serviran para adentrarnos en los conceptos de registro, stack frame, syscalls e instrucciones MIPS32. \\
Se utilizar\'a el programa GXemul para simular un entorno de desarrollo en una m\'aquina MIPS (corriendo una versi\'on del sistema operativo NetBSD) donde se compilar\'a y ejecutar\'a nuestro programa. 

\pagebreak




\section{Programa a implementar}
\textit
Se realiz\'o una versi\'on minimalista del programa wc. Este cuenta la cantidad de palabras, l\'ineas y caracteres dentro de un archivo, e imprime esas cantidades por stdout. El programa puede recibir 0, 1 o m\'as archivos. \\
En caso de no recibir un nombre de archivo, lee de stdin. Al recibir uno o m\'as archivos, informa el nombre de cada archivo junto con las cantidades, y el total para todos los archivos (s\'olo cuando se trata de m\'as de un nombre de archivo). \\
Devuelve 0 en caso de \'exito. Todos los errores deben escribirse en stderr \\


\pagebreak

\section{Desarrollo del Trabajo Pr\'actico}

\subsection{Consideraciones de Dise\~no}
En este programa hemos considerado que a\'un una l\'inea que no finaliza con \textit{"\textbackslash n"} es considerada como una l\'inea. Es decir, si por ejemplo, tenemos un archivo con el siguiente texto:

"lalala\textbackslash n
asd"

Se consideran 2 l\'ineas en nuestro programa. \\

Por otro lado, hemos considerado como separadores los siguientes caracteres:
\begin{itemize}
  \item Punto \textit{"."}
  \item Coma \textit{","}
  \item Punto y coma \textit{";"}
  \item Espacio \textit{" "}
  \item Tabulaci\'on \textit{"\textbackslash t"}
  \item Salto de l\'inea \textit{"\textbackslash n"}
\end{itemize}




\subsection{Explicaci\'on de la Implementaci\'on}
Describiremos a continuaci\'on las principales funcionalidades de nuestra implementaci\'on:

\subsubsection{main}
Su funci\'on principal es el parseo de las opciones ingresadas por el usuario por l\'inea de comando.

\subsubsection{procesarEntrada}
A partir de los archivos pasados por par\'ametro, {procesarEntrada} los abre y ejecuta el metodo wc sobre ellos. \\
Tambi\'en maneja el resultado de la invocaci\'on al metodo wc, que en caso de ser distinto a 0, implica que hubo un error en la lectura del archivo. \\
Si hay un problema al abrir alg\'un archivo o el metodo wc devolvi\'o distinto de 0, este muestra un mensaje de error y finaliza la ejecuci\'on.

\subsubsection{imprimir\_{}resultado}
Recibe un vector con contadores e imprime, seg\'un los flags ingresados por el usuario (w, l o c), el valor del contador elegido.

\subsubsection{wc}
Recibe un file descriptor y la direcci\'on de un vector de contadores. Lee el archivo caracter por caracter, e invoca al m\'etodo count para cada uno de estos. Adem\'as guarda el anterior caracter le\'ido en el stack y una variable que identifica si est\'a dentro de una palabra o no.

\begin{center}
\includegraphics[scale=0.50]{stackwc.png}
\end{center}


\subsubsection{count}
Este m\'etodo recibe el caracter le\'ido, la direcci\'on de un vector de contadores y un flag que indica si est\'a dentro de una palabra o no. \\
Identifica si el caracter es un separador y si lo es, resetea el flag de palabra y si el caracter es un "\textbackslash n" suma 1 al contador de lineas. \\
Por otro lado, si no es un separador, revisa el flag de palabra y si no es una palabra, suma 1 al contador de palabras, activando luego el flag de palabra. \\
Finalmente, suma 1 al contador de caracteres y devueve el estado final del flag de palabra.

\begin{center}
\includegraphics[scale=0.50]{stackcount.png}
\end{center}


\section{Generaci\'on de ejecutables y c\'odigo assembly}
Para correr el programa en NetBSD, debemos primero copiar los archivos \textit{tp1.c}, \textit{count.S} y \textit{wc.S}. \\
Luego en la terminal compilamos el programa, escribiendo la siguiente sentencia:

\begin{verbatim}
$ cc -g -Wall -O0 -o tp1 tp1.c wc.S count.S
\end{verbatim}


\pagebreak

\section{Corridas de prueba}
Comenzamos probando con todos los ejemplos provistos por la c\'atedra para verificar si obtenemos los resultados esperados. \\
Para visualizar el mensaje de ayuda, ejecutamos:
\begin{verbatim}
$ ./tp1 -h
\end{verbatim}

La consola nos muestra las siguientes opciones:


\begin{center}
\includegraphics[scale=0.60]{ayuda.png}
\end{center}

Luego ejecutamos:
\begin{verbatim}
$ echo "Don't panic" | ./tp1 
\end{verbatim}

El resultado esperado es: \\
1 \: 2 \: 12 
\begin{center}
\includegraphics[scale=0.50]{echo.png}
\end{center}

Observamos que el resultado es el mismo que el del ejemplo. \\

Probamos con la entrada de dos archivos juntos:
\begin{verbatim}
$ cat 1.in 
So long, and thanks for all the fish 
$ cat 2.in 
I think you ought to know I'm feeling very depressed 
$ ./tp1 1.in 2.in 
\end{verbatim}

El resultado esperado es: \\
1 \: 8 \: 37 \: 1.in \\
1 \: 10 \: 53 \: 2.in \\
2 \: 18 \: 92 \:	total \\
\underline{Nota}: Ac\'a al parecer hubo un error en el enunciado ya que 8 + 10 = 18 (12 en el enunciado) y 37 + 53 = 92 (65 en el enunciado).

\begin{center}
\includegraphics[scale=0.50]{cat.png}
\end{center}

Se observa que devuelve los resultados esperados. \\

Probamos usando dos flags en la misma instrucci\'on: \\
./tp1 -l -w 1.in \\

El resultado esperado es: \\
1 \: 8 \:	1.in 

\begin{center}
\includegraphics[scale=0.60]{tp1.png}
\end{center}
Finalmente, devuelve el resultado esperado. \\

Creamos un archivo random de 1024 bytes y ejecutamos el programa con la opci\'on de contar bytes o caracteres, pues al ser random no sabemos cuantas lineas o palabras tiene.
\begin{verbatim}
head -c 1024 /dev/urandom > random1024
./tp1 -c random1024 
\end{verbatim}
El resultado esperado es: \\
1024 \: random1024 \\
1024 \: TOTAL 

\begin{center}
\includegraphics[scale=0.50]{head.png}
\end{center}


Creamos un archivo de prueba con 3 lineas: 
\begin{verbatim}
cat > prueba1 
Esto es un archivo de prueba. linea 1 
linea 2 
linea 3 
\end{verbatim}

El resultado esperado es: \\
3 \: 12 \: 54 \: prueba1 \\
3 \: 12 \: 54 \: TOTAL 

\begin{center}
\includegraphics[scale=0.50]{catprueba.png}
\end{center}

Nuevamente, se observa que el resultado obtenido es igual al esperado. \\

Realizamos ahora la misma prueba, pero utilizando los 3 flags:
\begin{verbatim}
./tp1 -c -l -w prueba1
\end{verbatim}

\begin{center}
\includegraphics[scale=0.50]{tp1prueba.png}
\end{center}

Obtenemos el resultado correcto, pues es el mismo que el ejemplo anterior. \\

Creamos otro archivo de prueba y ejecutamos el programa con la opci\'on de caracteres para los archivos prueba1 y prueba2:
\begin{verbatim}
./tp1 -c prueba1 prueba2
\end{verbatim}

\begin{center}
\includegraphics[scale=0.50]{catprueba2.png}
\end{center}

Ahora solo ejecutaremos la opci\'on de lineas:
\begin{verbatim}
./tp1 -l prueba1 prueba2
\end{verbatim}

\begin{center}
\includegraphics[scale=0.50]{tp1prueba2.png}
\end{center}
Creamos otro archivo de prueba y ejecutamos el programa con la opci\'on de palabras con los archivos prueba1, prueba2 y prueba3:

\begin{center}
\includegraphics[scale=0.50]{catprueba3.png}
\end{center}
Probamos ejecutar el programa sin opciones con los tres archivos:
\begin{verbatim}
./tp1 prueba1 prueba2 prueba3
\end{verbatim}


\begin{center}
\includegraphics[scale=0.50]{tp1prueba3.png}
\end{center}

Se pueden realizar infinitas pruebas distintas para corroborar que el programa funciona adecuadamente. Estas son solo algunas de ellas, y las creemos suficientes como para asegurarnos del buen funcionamiento del mismo.

\pagebreak



\section{Problemas encontrados}
Al realizar las pruebas pudimos comprobar que al comparar nuestros resultados con los que obteniamos usando el wc de linux o NetBSD, habia diferencias.\\
Estas se deben principalmente a que los caracteres que nosotros consideramos como separadores no son necesariamente iguales a los que considera el wc de linux. As\'i, textos como ",,," son considerados palabras para wc de linux y no son considerados palabras para nuestro programa.\\
Asimismo, pudimos comprobar que wc de linux considera una l\'inea nueva, solo aquellas que finalizan en \textit{"\textbackslash n"} y nosotros contamos tambi\'en las que no finalizan con ese caracter.\\
Por otro lado, nos dimos cuenta que si el texto est\'a escrito con caracteres unicode, que son representados con m\'as de un caracter en los archivos, nuestro programa considerar\'a esos caracteres como diferentes, mientras que wc de linux los considera uno solo.

\pagebreak



\section{C\'odigo fuente}

\subsection{tp1.c}
\begin{verbatim}
#include <unistd.h>
#include <strings.h>
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <getopt.h>
#include <err.h>


#define WORDS_ACTION	1
#define LINES_ACTION	2
#define BYTES_ACTION	3

#define FILE_BUFFER     2048
extern int wc(int, unsigned long[]);
extern int count (char, unsigned long[], int);

void usage(char* pgname)
{
	fprintf(stdout,"Usage:\n");
	fprintf(stdout,"%s -h\n",pgname);
	fprintf(stdout,"%s -V\n",pgname);
	fprintf(stdout,"%s [options]\n",pgname);

	fprintf(stdout,"Options:\n");
	fprintf(stdout,"%s -V, --version\t\t\tPrint version and quit.\n",pgname);
	fprintf(stdout,"%s -h, --help\t\t\tPrint this information.\n",pgname);

	fprintf(stdout,"%s -w, --words\t\t\tPrint the number of words.\n",pgname);
	fprintf(stdout,"%s -l, --lines\t\t\tPrint the number of lines.\n",pgname);
	fprintf(stdout,"%s -c, --bytes\t\t\tPrint the number of bytes.\n",pgname);

	fprintf(stdout,"Examples:\n");

	fprintf(stdout,"%s foo\n",pgname);
	fprintf(stdout,"%s -l \n",pgname);

}

void imprimir_resultado(int actions[], unsigned long vector_contadores[], char* etiqueta){
	if(actions[0]!=0){
		fprintf(stdout,"%lu\t",vector_contadores[1]);
	}

	if(actions[1]!=0){
		fprintf(stdout,"%lu\t",vector_contadores[0]);
	}

	if(actions[2]!=0){
		fprintf(stdout,"%lu\t",vector_contadores[2]);
	}

	if(etiqueta != NULL){
		fprintf(stdout,"%s", etiqueta);
	}

	fprintf(stdout,"\n");


}

int procesar_entrada(int argc, char *argv[], int optind, int actions[]){
    unsigned long cant_files=(argc-optind);

    unsigned long totales[]={0,0,0};

    unsigned long contadores[]={0,0,0};

    int fdin=0;
    if (cant_files == 0){
    	wc(fdin, contadores);

    	imprimir_resultado(actions, contadores, NULL);

    } else {
    	int i=0;
    	for (i=0; i<cant_files; i++) {
    		fdin = open(argv[i+optind], O_RDONLY, 0);
    		if (fdin == -1) {
			    fprintf(stderr, "unable to open %s\n", argv[i+optind]);
			    usage(argv[0]);
			    exit(1);
		    }
    		int respuesta=wc(fdin, contadores);

		    if(respuesta!=0){
			    fprintf(stderr, "Error reading input: %s\n", argv[i+optind]);
			    exit(1);
		    }

    		imprimir_resultado(actions, contadores, argv[i+optind]);

    		totales[0]+=contadores[0];
    		totales[1]+=contadores[1];
    		totales[2]+=contadores[2];

      	contadores[0]=0;
      	contadores[1]=0;
      	contadores[2]=0;

    		close(fdin);
    	}

    	imprimir_resultado(actions, totales, "TOTAL");
    }

    return 0;
}

int main(int argc, char *argv[])
{
  int ch;

	static struct option longopts[] = {
           { "version", no_argument, NULL, 'V' },
           { "help", no_argument, NULL, 'h' },
           { "words", no_argument, NULL, 'w' },
           { "lines", no_argument, NULL, 'l' },
           { "bytes", no_argument, NULL, 'c' },
	         { NULL, 0, NULL, 0 }
  };

  int actions[3] = {0};

  while ((ch = getopt_long(argc, argv, "wlcVh", longopts, NULL)) != -1) {
    switch (ch) {
    	case 'l':
				actions[0]=LINES_ACTION;
				break;
			case 'w':
				actions[1]=WORDS_ACTION;
				break;
			case 'c':
				actions[2]=BYTES_ACTION;
				break;
      case 'h':
				usage(argv[0]);
      	exit(0);
	    	break;
			case 'V':
				printf("-- TP1 --\n");
				printf("Organizacion de Computadoras - 66.20\n");
				printf("Version 1.0\n");
				exit(0);
	    	break;
      default:
      	usage(argv[0]);
				exit(0);
				break;
    }
	}

  if (actions[0]==0 && actions[1]==0 && actions[2]==0){
  	actions[0]=LINES_ACTION;
  	actions[1]=WORDS_ACTION;
  	actions[2]=BYTES_ACTION;
  }

  return procesar_entrada(argc, argv, optind, actions);
}
\end{verbatim}

\pagebreak

\subsection{count.s}
\begin{verbatim}
#include <mips/regdef.h>

#define REG_FP	4
#define REG_GP	0	

#define SSIZE	8

#define ARG0	8
#define ARG1	12
#define ARG2	16
	
	.text
	.align	2
	.globl	count
	.ent	count

count:
	subu	sp,sp,SSIZE
	
	sw	$fp,REG_FP(sp)		#Saved Registers Area.
	sw	gp, REG_GP(sp)
	move	$fp, sp

					#Argument building area.
	sw	a0, ARG0($fp)		#ARG0=caracter
	sw	a1, ARG1($fp)		#ARG1=contadores
	sw	a2, ARG2($fp)		#ARG2=inword

	la	t0, separadores 	#Cargo la direccion de la cadena separadores
	lbu	t2, ARG0($fp)		#Cargo en t2 el caracter pasado como argumento
	lw	t6, ARG1($fp)		#Cargo la direccion del array de contadores en t7

separadores_loop:
	lbu	t1, 0(t0)
	beqz	t1, no_es_separador	#Si recorri todos los separadores y no lo encontre, no es un separador
	bne	t1, t2, loop_continue	#Si no es el separador actual, sigo revisando los otros separadores
	
	la	t3, newline		
	lbu	t4, 0(t3)		#Cargo el newline en t4

	bne	t2, t4, no_es_newline	#Chequeo si es un newline
	
	lw	t5, 4(t6)		#t4=contadores[1]
	addiu	t5, t5, 1		#t4++
	sw	t5, 4(t6)		#contadores[0]=t4 O sea, estoy sumando a la cantidad de lineas
	
no_es_newline:
	li	v0, 0
	b	loop_return
	
loop_continue:
	addiu	t0, t0, 1

	b	separadores_loop

no_es_separador:
	lw	t3, ARG2($fp)		

	bnez	t3, loop_return		#No es un separador, me fijo si inword es 0
	
	lw	t5, 0(t6)		#t5=contadores[0]
	addiu	t5, t5, 1		#t5++
	sw	t5, 0(t6)		#contadores[0]=t5 O sea, estoy sumando a la cantidad de palabras

	li	v0, 1			#Devolvemos inword=1

loop_return:

	lw	t5, 8(t6)		#t4=contadores[2]
	addiu	t5, t5, 1		#t4++
	sw	t5, 8(t6)		#contadores[2]=t4 O sea, estoy sumando a la cantidad de caracteres

	move	sp, $fp	
	lw	$fp, REG_FP(sp)
	addiu	sp, sp, SSIZE
	jr	ra
	
	.end count

.data
	separadores: .asciiz ".,;- \t\n"
	newline: .ascii "\n"
\end{verbatim}

\pagebreak

\subsection{wc.s}
\begin{verbatim}
#include <mips/regdef.h>
#include <sys/syscall.h>

#define REG_RA	32
#define REG_FP	28
#define REG_GP	24

#define INWORD	20
#define PREV_CAR 16

#define SSIZE	40

#define ARG0	40
#define ARG1	44
	
	.text
	.align	2
	.globl	wc
	.ent	wc

wc:
	subu	sp,sp,SSIZE
	
	sw	ra,REG_RA(sp)	#Saved Registers Area.
	sw	$fp,REG_FP(sp)
	sw	gp,REG_GP(sp)
	move	$fp,sp

				#Argument building area.
	sw	a0,ARG0($fp)	#ARG0=fd
	sw	a1,ARG1($fp)	#ARG1=contadores

	move	t0,zero		#t0=zero
	sw	t0,INWORD($fp)	#en 20+fp vamos a tener nuestra variable que va a determinar si estamos en una palabra o no.
				#La inicializamos en 0 ---> inword=0

	la	t0, newline		#Cargamos la direccion del caracter newline en t0
	lbu	t1, 0(t0)		#Cargamos el caracter newline en t1
	sw	t1, PREV_CAR($fp)	#Inicializamos la variable que guardara el caracter anterior con el valor newline

loop_leer_car:
	li 	v0, SYS_read
	lw 	a0, ARG0($fp)	#a0=fd
	la 	a1, car_buf
	li 	a2, 1
	syscall

	bgtu 	a3, zero, hubo_error	
	beq 	v0, zero, fin_loop_leer_car

	la	t0, car_buf		#Cargamos la direccion del buffer de caracteres
	lb	t1, 0(t0)		#Tomamos el byte que corresponde al caracter
	sb	t1, PREV_CAR($fp)	#Lo guardamos en el Local & Temporary Area, para tener cual fue el caracter anterior

	lb	a0, PREV_CAR($fp)	#Cargo en el registro $a0 el caracter
	lw	a1, ARG1($fp)	#Cargo en el registro $a1 la direccion de los contadores
	lw	a2, INWORD($fp)	#Cargo en el registro $a2 inword

	la	t9, count
	jalr	t9

	sw	v0, INWORD($fp)	#Guardamos el resultado del count en inword

	b	loop_leer_car


fin_loop_leer_car:
	
	la	t2, newline	
	lbu	t3, 0(t2)		#Cargo el caracter newline en t3

	lbu	t2, PREV_CAR($fp)	#Cargo el ultimo caracter en t2

	beq	t2, t3, es_newline	#Chequeo si es un newline. Si no es un newline debo sumar a la cantidad de lineas
	
	lw	t4, ARG1($fp)		#Cargo la direccion del array
	lw	t5, 4(t4)		#t4=contadores[1]
	addiu	t5, t5, 1		#t4++
	sw	t5, 4(t4)		#contadores[0]=t4 O sea, estoy sumando a la cantidad de lineas

es_newline:

	li v0, 0			#Retornamos 0 para indicar ejecucion exitosa

fin_wc:

	move	sp,$fp
	lw	ra, REG_RA(sp)
	lw	$fp, REG_FP(sp)
	addiu	sp, sp, SSIZE
	jr	ra
	
hubo_error:
	move v0, a3
	b	fin_wc
	.end wc 

	.data
	newline: .ascii "\n"
	car_buf: .byte
\end{verbatim}

\pagebreak

\section{Conclusiones}


La resoluci\'on del TP nos permiti\'o familiarizarnos a fondo con el conjunto de instrucciones de MIPS32, as\'i como tambi\'en con el concepto de ABI. La comprensi\'on de este ultimo concepto fue fundamental para el desarrollo de la soluci\'on, ya
que en m\'as de una oportunidad nuestro c\'odigo assembly fall\'o por estar mal diagramado el stack de la funci\'on a desarrollar.
Para la resoluci\'on de este TP tambi\'en tuvimos que adentrarnos en la utilizaci\'on de herramientas de debugging, como gdb, que permite ver el contenido del stack y de los registros. \\
Por \'ultimo, pudimos comprobar al realizar pruebas que nuestra soluci\'on no devuelve exactamente los mismos resultados que wc de linux/NetBSD y pudimos averiguar la causa de esta diferencia.



\pagebreak

\begin{thebibliography}{99}
	
\bibitem{GXEMUL} GXemul, http://gavare.se/gxemul/.

\bibitem{NETBSD} The NetBSD project, http://www.netbsd.org/.

\bibitem{WIKIUNIX} WC (Wikipedia), http://en.wikipedia.org/wiki/Wc\_(Unix).

\bibitem{LIBROC} Hennessy, John L. \& Patterson, David A.: \textquotedblleft Computer Architecture: A quantitive approach. Third Edition, 2003\textquotedblright .

\end{thebibliography}

\end{document}
